package com.github.hgkmail.hello.leetcode101.firstsearch;

//优先搜索：决策树遍历
public class LC695MaxAreaOfIsland {
    //辅函数
    public int dfs(int[][] grid, int[][] visited, int i, int j) {
        //已访问
        visited[i][j]=1;
        //若无效节点，直接返回
        if (grid[i][j]<=0) {
            return 0;
        }
        //若有效节点，尝试4个方向
        int area=1;
        if (i-1>=0 && visited[i-1][j]==0) { //边界判断、是否访问过判断
            area += dfs(grid, visited, i-1, j);
        }
        if (i+1< grid.length && visited[i+1][j]==0) {
            area += dfs(grid, visited, i+1, j);
        }
        if (j-1>=0 && visited[i][j-1]==0) {
            area += dfs(grid, visited, i, j - 1);
        }
        if (j+1< grid[0].length && visited[i][j+1]==0) {
            area += dfs(grid, visited, i, j + 1);
        }

        return area;
    }

    //主函数
    public int maxAreaOfIsland(int[][] grid) {
        //base case
        if (grid.length<=0 || grid[0].length<=0) {
            return 0;
        }
        //初始化全局状态变量
        //二维数组不是数组的数组，它就是二维的数组：type[] arrayName=new type[size1][size2]
        int[][] visited=new int[grid.length][grid[0].length];
        for (int i = 0; i < visited.length; i++) {
            for (int j = 0; j < visited[0].length; j++) {
                visited[i][j]=0; //未访问
            }
        }
        //遍历所有可搜索的位置
        int maxArea=0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                maxArea=Math.max(maxArea, dfs(grid, visited, i, j));
            }
        }

        return maxArea;
    }

    public static void main(String[] args) {
        System.out.println(new LC695MaxAreaOfIsland().maxAreaOfIsland(new int[][]{
                {0,0,1,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,1,1,0,1,0,0,0,0,0,0,0,0},{0,1,0,0,1,1,0,0,1,0,1,0,0},{0,1,0,0,1,1,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0}
        }));
    }
}
